1053. 交换一次的先前排列【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心

1. 📝 题目描述

• leetcode

给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大排列。

• 字典序更小
  • 考虑字符串 a 与 字符串 b，如果字符串 a 在 a 与 b 相异的第一处的字符在字母表上先于对应 b 在此处的字符出现，则称字符串 a 字典序小于 b。
  • 如果 a 或 b 其中较短的字符串为另一个字符串的前半部分，则较短的字符串字典序小于另一个字符串。

如果无法这么操作，就请返回原数组。

---

示例 1：

输入：arr = [3,2,1]
输出：[3,1,2]
解释：交换 2 和 1

示例 2：

输入：arr = [1,1,5]
输出：[1,1,5]
解释：已经是最小排列

示例 3：

输入：arr = [1,9,4,6,7]
输出：[1,7,4,6,9]
解释：交换 9 和 7

---

提示：

• 1 <= arr.length <= 10^4
• 1 <= arr[i] <= 10^4

2. 🎯 s.1 - 贪心

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var prevPermOpt1 = function (arr) {
  const n = arr.length
  let i = n - 2
  // find first decreasing pair from right
  while (i >= 0 && arr[i] <= arr[i + 1]) i--
  if (i < 0) return arr
  // find the largest element less than arr[i] to the right
  let j = n - 1
  while (arr[j] >= arr[i]) j--
  // skip duplicates
  while (j > 0 && arr[j] === arr[j - 1]) j--
  const tmp = arr[i]
  arr[i] = arr[j]
  arr[j] = tmp
  return arr
}

• 时间复杂度：$O(n)$，其中 $n$ 是数组的长度
• 空间复杂度：$O(1)$，原地修改

算法思路：

• 从右向左找第一个“递减”位置 i，即 arr[i] > arr[i+1]
• 在 i 右侧找小于 arr[i] 的最大元素位置 j，跳过重复元素
• 交换 arr[i] 和 arr[j]，即得到字典序最大的前一个排列